import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        if (size == 0 || num.length < size) {
            return new ArrayList<Integer>();
        }

        ArrayList<Integer> arr = new ArrayList<Integer>();
        Deque<Integer> deque = new ArrayDeque<Integer>();

        for (int i = 0; i < size; i++) {
            while (!deque.isEmpty() && num[deque.peekLast()] <= num[i]) {
                deque.removeLast();
            }
            deque.addLast(i);
        }

        for (int i = size; i < num.length; i++) {
            arr.add(num[deque.peekFirst()]);

            while (!deque.isEmpty() && deque.peekFirst() <= i - size) {
                deque.removeFirst();
            }

            while (!deque.isEmpty() && num[deque.peekLast()] <= num[i]) {
                deque.removeLast();
            }
            deque.addLast(i);
        }
        arr.add(num[deque.peekFirst()]);

        return arr;
    }
}
